package Demo1;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-08-24
 * Time: 14:08
 */
public class Test {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };

    //二叉树的锯齿状遍历
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

    boolean flag = true;//判段是否需要逆置

    List<List<Integer>> list = new LinkedList();
    if(root == null) return list;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);

    while(!queue.isEmpty()){
        int size = queue.size();

        List<Integer> ret = new LinkedList<Integer>();
        while(size != 0){
            //读取元素
            TreeNode tmp = queue.poll();
            if(tmp.left != null){
                queue.offer(tmp.left);
            }

            if(tmp.right != null){
                queue.offer(tmp.right);
            }

            ret.add(tmp.val);
            size--;
        }

        if(flag){
            flag = false;
        }else{
            Collections.reverse(ret);//逆置
            flag = true;
        }
        list.add(ret);
    }
    return list;
}
    //路径总和 II
    public List<List<Integer>> list = new LinkedList<>();
    public void Linked(TreeNode root,int targetSum,List<Integer> ret){
        if(root == null) return;
        //判段叶子节点
        List<Integer> tmp = new LinkedList<Integer>(ret);
        if(root.left == null && root.right == null){
            if(targetSum == root.val){
                tmp.add(root.val);
                list.add(tmp);
            }
            return;
        }
        //非叶子节点
        tmp.add(root.val);
        Linked(root.left,targetSum - root.val,tmp);
        Linked(root.right,targetSum - root.val,tmp);
    }
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root == null) return list;
        Linked(root,targetSum,new LinkedList<Integer>());
        return list;
    }

    //填充每一个节点的下一个右侧节点指针
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<Node>();
        if(root == null) return root;
        queue.offer(root);
        while(!queue.isEmpty()){
            //获取队列大小
            int size = queue.size();
            while(size != 0){

                //弹出对头元素
                Node tmp = queue.poll();

                //修改next指向
                if(size != 1){
                    tmp.next = queue.peek();
                }

                if(tmp.left != null){
                    queue.offer(tmp.left);
                }

                if(tmp.right != null){
                    queue.offer(tmp.right);
                }
                size--;
            }
        }
        return root;
    }

    public static void main(String[] args){
        List<Integer> list1 = new LinkedList<>();
        list1.add(1);
        list1.add(2);
        List<Integer> list2 = new LinkedList<>(list1);
        System.out.println(list2);
        System.out.println(list1 == list2);
    }
}
